#include<iostream>
#include<vector>
using namespace std;

int lastStoneWeightII(vector<int>& stones) {
	int length = stones.size();
	int sum = 0;
	for (int i = 0; i < length; i++)
	{
		sum += stones[i];
	}
	int all = sum;
	sum /= 2;
	vector<vector<int>>dp(sum+1, { 0,0 });
	dp[0][0] = 1;
	for (int i = 0; i < length; i++)
	{
		for (int j = 0; j < sum + 1; j++)
		{
			int sz = j - stones[i];
			dp[j][(i + 1) % 2] = max(dp[j][i % 2], dp[j][(i + 1) % 2]);
			if (sz >= 0)
			{
				dp[j][(i + 1) % 2] = max(dp[j][(i + 1) % 2], dp[sz][i % 2]);
			}
		}
	}
	int number = 0;
	for (int i = 0; i < sum + 1; i++)
	{
		if (dp[i][0] || dp[i][1])
		{
			number = i;
		}
	}
	return all - 2 * number;
}
